package com.atguigu.algorithm;

import java.util.Arrays;

/**
 * @Author: shenhao
 * @CreatTime: 2024/10/31 0:01
 * @Version: 1.0
 * 删除有序数组中的重复项
 * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，
 * 使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
 * 然后返回 nums 中唯一元素的个数。
 */
public class LeetCode026 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 3, 4, 5, 5, 7, 8, 9};
        int length = removeDuplicates(nums);
        System.out.println(length);
        System.out.println(Arrays.toString(nums));
    }
    // 自己写的都是移动,效率低, 能不能互换位置
    public static int removeDuplicates(int[] nums) {
        /*int i = 0; int j = 1; int k = nums.length-1;
        while (j <= k) {
            if (nums[j] != nums[i]) {
                i=j;
                j++;
            }else {
                int index = j;
                while (index < k){
                    nums[index] = nums[index+1];
                    index++;
                }
                k--;
            }
        }
        return ++k;*/
        // 倒着遍历,效率也没有快多少
        /*int right = nums.length - 1;
        int left = nums.length - 2;
        int length = nums.length - 1;
        while (left >= 0) {
            if (nums[left] == nums[right]) {
                while (right != length) {
                    nums[right] = nums[right + 1];
                    right++;
                }
                length--;
            }
            right = left;
            left--;
        }
        return length + 1;*/
        //本题优雅口诀 O(n) 删除有序数组中的重复项
        //快慢相等值不变, 慢针不动快针走
        // 快慢不等值, 我是题型一, 慢针向前一步走,快针赋值给慢针, 快针向前一步走
        // {1, 1, 3, 4, 5, 5, 7, 8, 9};
        int fast=0,slow=0;
        while(fast<nums.length){
            /*if (nums[fast]==nums[slow]){
                fast++;
            }else {
                slow++;
                nums[slow] = nums[fast];
                fast++;
            }*/
            if (nums[fast]!=nums[slow]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return ++slow;
    }
}
